import java.util.Arrays;

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 排序，把可能有的负数排到前面
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 贪心：如果是负数，而k还有盈余，就把负数反过来
            if (nums[i] < 0 && k > 0) {
                nums[i] = -1 * nums[i];
                k--;
            }
            sum += nums[i];
        }
        Arrays.sort(nums);
        // 如果k没剩，那说明能转的负数都转正了，已经是最大和，返回sum
        // 如果k有剩，说明负数已经全部转正，所以如果k还剩偶数个就自己抵消掉，不用删减，如果k还剩奇数个就减掉2倍最小正数。
        return sum - (k % 2 == 0 ? 0 : 2 * nums[0]);
    }
}


class Solution1 {
    public String[] sortPeople(String[] names, int[] heights) {
        int n=heights.length;
        Integer[] index=new Integer[n];  //注意必须是包装类型
        for(int i=0;i<n;i++) index[i]=i;
        Arrays.sort(index, (a, b) -> heights[b] - heights[a]);
        // Arrays.sort(index,(a,b)->heights[b]-heights[a]);
        String[] ret=new  String[n];
        for(int i=0;i<n;i++) ret[i]=names[index[i]];
        return ret;

    }
}


class Solution2 {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n=nums1.length;
        int[] ret=new int[n];

        Integer[] index2=new Integer[n];

        for(int i=0;i<n;i++){

            index2[i]=i;
        }


        Arrays.sort(nums1);
        Arrays.sort(index2,(a,b)->nums2[a]-nums2[b]);
        int left=0;
        int right=n-1;

        for(int i=0;i<n;i++){
            if(nums1[i]>nums2[index2[left]]) ret[index2[left++]]=nums1[i];
            else ret[index2[right--]]=nums1[i];

        }

        return ret;


    }
}


class Solution3 {
    public int longestPalindrome(String s) {
        int ret=0;
        int[] arr=new int[128];
        char[] ss=s.toCharArray();
        for(char c:ss){
            arr[c]++;
        }

        boolean f=false;

        for(int n:arr){
            if(n!=0){
                if(n%2==0) ret+=n;
                else{
                    ret+=n-1;
                    f=true;

                }
            }
        }
        if(f) return ret+1;
        return ret;

    }
}